-- specification du paquetage dictionnaires
-- Algo, Ensimag 1A-apprentissage, PA2
-- 2009-2010, KA

-- A COMPLETER !!

with Ada.Text_Io, Ada.Unchecked_Deallocation;
with Ada.Numerics.Elementary_Functions;

package body Dictionnaires is

   -- TYPE DICTIONNAIRE / TABLE -------------------------------------------

   -- listes chainees des entrees
   type Cell;

   type Liste is access Cell;

   type Cell is record
      motC : Mot;
      defC : Definition;
      suivant : Liste;
   end record;


   --  type Dictionnaire is access Table;
   type Table is array(Natural range <>) of Liste;
   procedure Liberer_Table is new Ada.Unchecked_Deallocation(Table, PTable);
   -- liberer cellule
   procedure Liberer_Cell is new Ada.Unchecked_Deallocation(Cell, Liste);

   -- MOTS ----------------------------------------------------------------
   function Cree_Mot(S: String) return Mot is
      Res: Mot(S'Length);
   begin
      if S'Length=0 then raise Erreur_Dico; end if;
      Res.S := S;
      return Res;
   end Cree_Mot;

   function Hash(M: Mot) return Natural is
   begin
      return Hash(M.S);
   end Hash;

   procedure Put(M: in Mot) is
   begin
      Ada.Text_Io.Put(M.S);
   end Put;

   -- fonction pas très utile lorsque l'on a des listes triées
   -- function Egal(Gauche, Droite: Mot) return Boolean is
   -- begin
   --   return Droite.S = Gauche.S;
   -- end Egal;

   --------- DEFINITIONS -----------------------------------------------------
   function Cree_Def(S: String) return Definition is
      Res: Definition(S'Length);
   begin
      if S'Length=0 then raise Erreur_Dico; end if;
      Res.S := S;
      return Res;
   end;

   procedure Put(D: in Definition) is
   begin
      Ada.Text_Io.Put(D.S);
   end;

   -- DICTIONNAIRE -------------------------------------------------------

   function Cree_Dico return Dictionnaire is
      Dico: Dictionnaire := (0, new Table(1..Taille_Redim));
   begin
      return Dico;
   end;

   procedure Vider(Dico: in out Dictionnaire) is
      Courant: Liste;
      CourantSuiv : Liste;
   begin
      for I in Dico.Tab'Range loop
        if Dico.Tab(I) /= null then
	  Courant := Dico.Tab(I).suivant;
          Liberer_Cell(Dico.Tab(I));
          while Courant /= null loop
            CourantSuiv := Courant.suivant;
            Liberer_Cell(Courant);
            Courant := CourantSuiv;
          end loop;
        end if;
      end loop;
      Dico.Taille := 0;
   end;

   -- redimensionne la table de hachage : la nouvelle table a pour
   -- taille 'Taille', tous les elements sont recopies dans la table.
   procedure Redim(Dico: in out Dictionnaire; Taille: in Positive) is
      NewDico: Dictionnaire := (0, new Table(1..Taille));
      Courant: Liste;
   begin
      if Debug then
        Ada.Text_IO.New_Line;
        Ada.Text_IO.Put_Line("Contenu du dico avant redim");
        Put(Dico);
	Ada.Text_IO.New_Line;
      	Ada.Text_IO.Put_Line("On redimensionne notre dictionnaire avec la taille : " & Integer'Image(Taille));
      end if;
      for I in Dico.Tab'Range loop
        Courant := Dico.Tab(I);
        while Courant /= null loop
          Insere(NewDico, Courant.motC, Courant.defC);
          Courant := Courant.Suivant;
        end loop;
      end loop;
      Vider(Dico);
      Liberer_Table(Dico.Tab);
      Dico := NewDico;
      if Debug then
        Ada.Text_IO.New_Line;
	Ada.Text_IO.Put_Line("Contenu du dico après redim");
        Put(Dico);
        Ada.Text_IO.New_Line;
      end if;
   end;

   -- Trouve = 'M est dans D'
   -- si Trouve, alors Def est la definition associee a M
   -- sinon Def n'a pas de valeur specifiee
   procedure Trouve(D: in Dictionnaire;
                    M: in Mot;
                    Trouve: out Boolean; Def: out definition) is
      Courant : Liste;
      I : Natural;
   begin
      Trouve := false;
      I := Hash(M) mod D.Tab'Length + 1;
      Courant := D.Tab(I);
      while Courant /= null loop
        exit when Courant.motC.S >= M.S;
        Courant := Courant.suivant;
      end loop;
      -- Soit on a trouvé le mot et donc Courant.motC.S = M.S soit on ne la pas trouvé
      -- et donc Courant = null
      if Courant /= null and then Courant.motC.S = M.S then
        Trouve := true;
        Def := Courant.defC;
      end if;
   end Trouve;

   -- si M est dans D, cela remplace la definition de M par Def (mise a jour)
   -- sinon, M est insere dans le dictionnaire D
   procedure Insere(D: in out Dictionnaire; M: in Mot; Def: in Definition) is
      Courant : Liste;
      NouveauMot : Liste;
      I : Natural;
   begin
      I := Hash(M) mod D.Tab'length + 1;
      if Debug then
        Ada.Text_Io.Put_Line("Mot à insérer : " & M.S);
        Ada.Text_Io.Put_Line("Définition à insérer : " & Def.S);
      end if;
      if D.Tab(I) = null or (D.Tab(I) /= null and then D.Tab(I).motC.S >= M.S) then
        -- la liste est nulle donc notre nouveau mot est le premier élément
	-- de la liste
        if D.Tab(I) /= null and then D.Tab(I).motC.S = M.S then
          D.Tab(I).defC := Def;
        else
          D.Tab(I) := new Cell'(M, Def, D.Tab(I));
          D.Taille := D.Taille + 1;
        end if;
      else
        -- la liste n'est pas nulle et on n'insere pas en premiere position
        Courant := D.Tab(I);
        while Courant.suivant /= null and then Courant.suivant.motC.S < M.S loop
          Courant := Courant.suivant;
        end loop;
        -- Courant.suivant.motC.S >= M.S, on remplace la definition si le mot existe déja
        -- ou on ajoute la nouvelle définition
        if Courant.suivant /= null and then Courant.suivant.motC.S = M.S then
          Courant.suivant.defC.S := Def.S;
        else
          -- courant.suivant peut etre égal à null
          -- on ajoute la nouvelle définition
          NouveauMot := new Cell'(M, Def, Courant.suivant);
          Courant.suivant := NouveauMot;
          D.Taille := D.Taille + 1;
        end if;
      end if;
      -- on regarde s'il faut redimensionner
      if (D.Tab'Length * FacteurChargeInsertion) < D.Taille then
        Redim(D, 2*D.Tab'Length);
      end if;
   end Insere;

   -- Trouve = 'M est dans D'
   -- si Trouve, alors Def est la definition associee a M
   -- sinon Def n'a pas de valeur specifiee
   procedure Supprime(D: in out Dictionnaire;
                      M: in Mot;
                      Trouve: out Boolean; Def: out definition) is
      Courant : Liste;
      Save : Liste;
      I : Natural;
   begin
      -- on regarde s'il faut redimensionner
      if (D.Tab'Length / FacteurChargeSuppression) = D.Taille then
        Redim(D, (D.Tab'Length / FacteurChargeSuppression));
      end if;
      I := Hash(M) mod D.Tab'Length + 1;
      if Debug then
        Ada.Text_Io.Put_Line("Mot à supprimer : " & M.S & " Indice : " & Integer'Image(I));
      end if;
      Trouve := false;
      if D.Tab(I) /= null then
        if D.Tab(I).motC.S = M.S then
          -- le mot est le premier élement de la liste
          Trouve := True;
          Save := D.Tab(I);
          Def := Save.defC;
          D.Tab(I) := D.Tab(I).suivant; 
          Liberer_Cell(Save);
          D.Taille := D.Taille - 1;
        else
          Courant := D.Tab(I);
          -- on parcours la liste pour trouver le mot
          while Courant.suivant /= null and then Courant.suivant.motC.S < M.S loop
            Courant := Courant.suivant;
          end loop;
          if Courant.suivant /= null and then Courant.suivant.motC.S = M.S then
            Trouve := True;
            Save := Courant.suivant;
            Courant.suivant := Courant.suivant.suivant;
            Def := Save.defC;
            Liberer_Cell(Save);
            D.Taille := D.Taille - 1;
          end if;
        end if;
      end if;
   end Supprime;


   -- entrees / sorties / statistiques --------
   procedure Remplit_Dico(F: in out Ada.Text_Io.File_Type;
                          Dico: out Dictionnaire) is separate;

   procedure Supprime_Mots(F: in out Ada.Text_Io.File_Type;
                           Dico: in out Dictionnaire) is separate;

   procedure Put(D: Dictionnaire) is
      Courant : Liste;
   begin
      Ada.Text_Io.New_Line;
      for I in D.Tab'Range loop
        Courant := D.Tab(I);
        while Courant /= null loop
          Put (Courant.motC);
          if Debug Then
             Ada.Text_Io.Put(" Indice : " & Integer'Image(I));
          end if;
          Ada.Text_Io.New_Line;
          Courant := Courant.suivant;
        end loop;
      end loop;
   end Put;

   -- statistiques
   procedure Dispersion (Dico: in Dictionnaire) is
       Moy: Float; --lgr moy des listes de la table
       Ecart_Type: Float; -- ecart type
       Lgrs: array(Dico.Tab'Range) of Natural;  -- longueurs des
                                               -- listes de la table

       procedure Calcule_Lgrs(Dico: in Dictionnaire) is
	  cpt : Natural;
          Courant : Liste;
       begin
          for I in Dico.Tab'Range loop
            Courant := Dico.Tab(I);
            cpt := 0;
            while Courant /= null loop
              cpt := cpt + 1;
              Courant := Courant.suivant;
            end loop;
	    Lgrs(I) := cpt;
          end loop;
       end;

    begin -- dispersion
       Calcule_Lgrs(Dico);
      -- moyenne
       Moy := Float(Dico.Taille) / Float(Dico.Tab'Length);
      -- ecart type
       Ecart_Type := 0.0;
       for I in Lgrs'Range loop
          Ecart_Type := Ecart_Type
            + (Float(Lgrs(I)) - Moy)*((Float(Lgrs(I)) - Moy));
       end loop;
       Ecart_Type := Ada.Numerics.Elementary_Functions.Sqrt
         (Ecart_Type / Float(Lgrs'Length));

       Ada.Text_Io.Put_Line("Nombre de mots : " & Integer'Image(Dico.Taille));
       Ada.Text_Io.Put("Forme de la table : ");
       for I in Lgrs'Range loop
          Ada.Text_Io.Put(Integer'Image(Lgrs(I)) & " || ");
       end loop;
       Ada.Text_Io.Put_Line("Moyenne : " & Float'Image(Moy));
       Ada.Text_Io.Put_Line("Ecart type : " & Float'Image(Ecart_Type));
       Ada.Text_Io.New_Line;

    end Dispersion;

    function GetTaille(Dico: in Dictionnaire) return Natural is
    begin
       return Dico.Taille;
    end GetTaille;

    function GetLength(Dico: in Dictionnaire) return Natural is
    begin
       return Dico.Tab'Length;
    end GetLength;

end Dictionnaires;
